{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.5"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python3",
   "language": "python",
   "display_name": "Python 3"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'sdf' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-1-a0571c5b9493>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0msdf\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'sdf' is not defined"
     ]
    }
   ],
   "source": [
    "# 17.电话号码的字母组合\n"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。\n",
    "\n",
    "给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。\n",
    "\n",
    "\n",
    "![jpg](https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/17_telephone_keypad.png)\n",
    "\n",
    "示例:\n",
    "\n",
    "输入：\"23\"\n",
    "输出：[\"ad\", \"ae\", \"af\", \"bd\", \"be\", \"bf\", \"cd\", \"ce\", \"cf\"].\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "![png](https://pic.leetcode-cn.com/0ac574ab37f620221e702f57d6c4ffd0ba246abe41c43f9fc9637ab8f3365377-image.png)\n"
   ]
  },
  {
   "source": [
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        phone = {'2': ['a', 'b', 'c'],\n",
    "                 '3': ['d', 'e', 'f'],\n",
    "                 '4': ['g', 'h', 'i'],\n",
    "                 '5': ['j', 'k', 'l'],\n",
    "                 '6': ['m', 'n', 'o'],\n",
    "                 '7': ['p', 'q', 'r', 's'],\n",
    "                 '8': ['t', 'u', 'v'],\n",
    "                 '9': ['w', 'x', 'y', 'z']}\n",
    "                \n",
    "        def backtrack(combination, next_digits):\n",
    "            # if there is no more digits to check\n",
    "            if len(next_digits) == 0:\n",
    "                # the combination is done\n",
    "                output.append(combination)\n",
    "            # if there are still digits to check\n",
    "            else:\n",
    "                # iterate over all letters which map \n",
    "                # the next available digit\n",
    "                for letter in phone[next_digits[0]]:\n",
    "                    # append the current letter to the combination\n",
    "                    # and proceed to the next digits\n",
    "                    backtrack(combination + letter, next_digits[1:])\n",
    "                    \n",
    "        output = []\n",
    "        if digits:\n",
    "            backtrack(\"\", digits)\n",
    "        return output\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    Sol = Solution()\n",
    "    end = Sol.letterCombinations(\"23\")\n",
    "    print(end)\n"
   ],
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "text": [
      "['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']\n"
     ],
     "output_type": "stream"
    }
   ],
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "execution_count": 4
  }
 ]
}